متا دوم (META II)

متا دوم (به انگلیسی: META II) یک زبان برنامه‌نویسی/دامنه-اختصاصی(DSL) برای نوشتن کامپایلرها است. META II در سال ۱۹۶۳–۱۹۶۴ توسط دیوی وال شورور(Dewey Val Schorre) در UCLA ایجاد شده‌است. META II از آنچه Schorre آ را معادلات نحوی(syntax equations) نامیده استفاده می‌کند. عملکرد آن به سادگی به شرح زیر است:

هر معادله نحوی(syntax equation) به یک زیرواحد بازگشتی ترجمه می‌شود که رشته ورودی را برای یک ساختار عبارت خاص آزمایش می‌کند و در صورت یافتن آن را حذف می‌کند.^[۱]

برنامه‌های META II به یک زبان بایت کد تفسیر شده (interpreted byte code) تبدیل/کامپایل می‌شوند. کامپایلرهای VALGOL و SMALGOL که توانایی‌های آن را نشان می‌دهند، که به زبان META II نوشته شده‌اند،^[۱]^[۲] VALGOL یک زبان جبری ساده است که به منظور نشان دادن META II طراحی شده‌است. SMALGOL زیر مجموعه نسبتاً بزرگی از ALGOL 60 بود.

چند نکته

META II برای اولین بار در META I نوشته شده‌است،^[۳] نسخه ای دست‌ساز از META II. روشن نیست که آیا META I پیاده‌سازی کامل META II بود یا یک زیر مجموعه مورد نیاز از زبان META II که برای تهیه کامپایلر نهایی META II لازم بود.

META II مستندات خود را شبیه BNF توصیف می‌کند. امروزه BNF به عنوان گرامر تولید، معرفی می‌شود. META II یک گرامر تحلیلی است. در سند TREE-META این زبانها به عنوان گرامرهای کاهشی توصیف شده‌اند.

به عنوان مثال، در BNF، یک عبارت ریاضی به صورت زیر تعریف می‌شود:

<expr> := <term> | <expr> <addop> <term>

قوانین BNF امروزه قوانینی سازنده هستند که بیان می‌کند چگونه قطعات تشکیل دهنده ممکن هست به شکل یک ساختار زبان معتبر مونتاژ شود. یک تجزیه کننده بر خلاف ساخت‌های زبان عمل تجزیه را انجام می‌دهد. META II مبتنی بر پشته(stack based) و تجزیه کننده (functional parser programming language) است که شامل بخشنامه خروجی می‌باشد. در META II، ترتیب آزمایش توسط معادله مشخص شده‌است. META II مانند سایر زبان‌های برنامه‌نویسی، پشته‌های را سر ریز می‌کند تا بازگشت به چپ را انجام دهند. META II از یک اپراتور دنباله $ (صفر یا بیشتر) استفاده می‌کند. معادله تجزیه تحلیل expr نوشته شده در META II یک عبارت شرطی است که از چپ به راست ارزیابی می‌شود:

expr = term
    $( '+' term .OUT('ADD')
    / '-' term .OUT('SUB'));

در بالا معادله expr توسط عبارت در سمت راست '=' تعریف شده‌است. ارزیابی چپ به راست از عبارت "=" اولین چیزی است که باید آزمایش شود. اگر term بازگردد expr شکست می‌خورد. اگر یک term موفق به رسمیت شناخته شود، ما باید به مقدار نا متناهی $، صفر یا حلقه‌های بیشتر را وارد کنیم، اگر اولین گزینه را برای "+" آزمایش کردیم، اگر جایگزین ناموفق باشد "-" تلاش می‌شود و در آخر اگر "-" شناخته نشود، حلقه با بازگشت expr خاتمه می‌یابد. موفقیت با شناسایی یک term o,hin f,n. اگر "+" یا "-" موفقیت‌آمیز باشد، term خوانده می‌شود؛ و در صورت موفقیت حلقه تکرار می‌شود. معادله expr را می‌توان با استفاده از گروه‌بندی تو در تو نیز بیان کرد:

expr = term $(('+' / '-') term);

عناصر تولید کد برای ساده کردن مثال کنار گذاشته شدند. با توجه به مجموعه محدود شخصیت‌ها، شخصیت رایانه‌های اولیه / به عنوان گزینه جایگزین یا اپراتور مورد استفاده قرار گرفت. اپراتور حلقه $ ، برای مطابقت با صفر یا موارد دیگر استفاده می‌شود:

expr = term $('+' term .OUT('ADD')
      /('-' term .OUT('SUB'));

موارد بالا می‌تواند به زبان انگلیسی بیان شود: expr جمله ای است که ارزش ۰ یا بیشتر دارد (به term مثبت یا term منفی). Schorre این کار را به عنوان کمک به کارایی توصیف می‌کند، اما برخلاف یک کامپایلر نزولی بازگشتی، این اطمینان را نیز می‌دهد که شرکت پذیری عملیات حسابی نیز صحیح است:

expr = term $(
     '+' term .OUT('ADD') /
     '-' term .OUT('SUB'));
term = factor $(
     '*' factor .OUT('MPY')
    /'/' factor .OUT('DIV')
   );
factor = ( .ID
     / .NUMBER
     / '(' expr ')')
     ( '^' factor .OUT('EXP')
     / .EMPTY);

با توانایی بیان دنباله با یک حلقه یا یک راست ("tail") ترتیب ارزیابی می‌تواند کنترل شود.

قوانین نحوی به نظر می‌رسد قابل اجرا هستند اما در واقع توجه به مشخصات معنایی آنها ضروری است.

عملگر

META II کد اسمبلی را برای یک دستگاه پشته تولید می‌کند. ارزیابی این مانند استفاده از ماشین حساب RPN است.

expr = term
    $('+' term .OUT('ADD')
    /'-' term .OUT('SUB'));
term = factor
    $('*' factor .OUT('MPY')
    / '/' factor .OUT('DIV'));
factor = (.ID .OUT('LD ' *)
     / .NUM .OUT('LDL ' *)
     / '(' expr ')')
     ( '^' factor .OUT('XPN'/.EMPTY);

در بالا. ID و NUM به عنوان توکن‌های شناخته شده هستند. * در. OUT کد تولید آخرین مرجع شناخته شده را ارجاع می‌دهد. در تشخیص شماره با(*NUM .OUT('LDL' دستورالعمل تحت اللفظی عدد را دنبال می‌کند. یک عبارت:

(۳*a^2+5)/b

تولید خواهد کرد:

   LDL 3
   LD a
   LDL 2
   XPN
   MPY
   LDL 5
   ADD
   LD b
   DIV

META II اولین نسخه مستند شده از metacompiler است،^{[notes ۱]} که در یکی از اولین نمونه‌های ماشین مجازی ، به کد دستگاه کامپایل می‌شود.

مقاله خود یک گوهر شگفت‌انگیز است که شامل نمونه‌های بسیار خوبی است، از جمله بوت استارتاپ META II (همه این کارها در 8K (شش بیت بایت) انجام گرفته‌است) " -- Alan Kay

مقاله اصلی به‌طور آزاد در دسترس نیست، اما در مجله Doctor Dobb (آوریل ۱۹۸۰) مجدداً چاپ شد. کد منبع رونویسی در زمانهای مختلف (احتمالاً توسط گروه کاربری CP / M) در دسترس است. در این مقاله لیستی از توضیحات متا دوم وجود دارد، این در اصل می‌تواند به صورت دستی پردازش شود تا بتواند یک برنامه قابل تفسیر را در کدهای ماشین مجازی ارائه دهد. اگر این فرار کند و بازده یکسانی تولید کند، اجرای آن صحیح بود. META II اساساً اثبات یک مفهوم بود. پایه و اساسی که برای کارها از آن استفاده می‌شود.

META II به عنوان یک زبان استاندارد ارائه نمی‌شود، اما به عنوان نقطه عزیمت از آنجا که کاربر ممکن است " زبان " META خود را توسعه دهد هائز اهمیت است.^[۱]

بسیاری از META «زبان ها» تبعیت کردند. شورور برای کار در شرکت توسعه سیستم، جایی که عضو پروژه کامپایلر برای نوشتن و اجرای کامپایلرها (CWIC) بود، رفت. زبان SYNTAX CWIC که بر روی META II ساخته شده‌است و اپراتورهای جایگزین بکگراند مثبت و منفی به نظر می‌رسد که اپراتورها و معادلات توکن برنامه‌ریزی شده را دارند. . OUT و . عملیات LABEL حذف شد و عملیات تغییر شکل را جمع‌آوری کرد :<node> و !<number> اضافه شد. زبان GENERATOR مبتنی بر LISP 2، درختان تولید شده توسط زبان تجزیه کننده SYNTAX را پردازش می‌کند. برای تولید کد، عملکرد ژنراتور که در یک معادله SYNTAX قرار داده شده‌است فراخوانی می‌شود. این زبانها توسط اعضای زیر گروه LA ACM SIGPLAN در Syntax Directed Compilers ساخته شده‌اند. قابل توجه است که شورور چطور به زبان META II فکر کرد:

اصطلاح «زبان» META با META با حروف بزرگ برای مشخص کردن هر زبان نوشتاری کامپایلر که چنین توسعه یافته‌است استفاده می‌شود.^[۱]

همچنین شورور، META II را به عنوان پایه ای توصیف می‌کند که از آن «دیگر» زبان‌های META ساخته می‌شود.

همچنین مشاهده کنید

OMeta
TREE-META

یادداشت

↑ Ignoring META I which is only mentioned in passing in the META II document.

منابع

↑ ^۱٫۰ ^۱٫۱ ^۱٫۲ ^۱٫۳ META II A SYNTAX-ORIENTED COMPILER WRITING LANGUAGE (Dewey Val Schorre UCLA Computing Facility 1964)
↑ Dewey, Val Schorre (1963). "A Syntax - Directed SMALGOL for the 1401,". ACM Natl. Conf. , Denver, Colo.
↑ Dewey, Val Schorre (1963). META II: a syntax-oriented compiler writing language (PDF). UCLA: UCLA Computing Facility.

پیوند به بیرون

[META1-4] Ignoring META I which is only mentioned in passing in the META II document.

[METAII-1] ۱٫۰ ^۱٫۱ ^۱٫۲ ^۱٫۳ META II A SYNTAX-ORIENTED COMPILER WRITING LANGUAGE (Dewey Val Schorre UCLA Computing Facility 1964)

[SMALGOL-2] Dewey, Val Schorre (1963). "A Syntax - Directed SMALGOL for the 1401,". ACM Natl. Conf. , Denver, Colo.

[Schorre-3] Dewey, Val Schorre (1963). META II: a syntax-oriented compiler writing language (PDF). UCLA: UCLA Computing Facility.

[۱]

[۲]

[۳]

[notes ۱]